\input{../slidesComun}

\title[10. Abstract algebra]{Chapter 10. Abstract algebra}  
\COSS

% ==============================================
\begin{frame}\frametitle{References} 

\begin{figure}
	\includegraphics[height=5cm]{figFraleigh.jpg}
\end{figure}
J.B. Fraleigh. A first course in Abstract Algebra. Pearson, 7th Ed. (2002)

\end{frame}

% ==============================================
\setnextsection{10}

\section{Abstract algebra} 
\subsection{Sets} 
\Outline

\begin{frame}\frametitle{Sets}

\begin{ceudef}[Set]
	A \textbf{set} is a well-defined collection of \textbf{elements}. We denote the different elements as $a\in S$.
\end{ceudef}

\begin{ceudef}[Empty set]
	The only set without any element is the \textbf{empty set} ($\emptyset$).
\end{ceudef}

\begin{block}{Describing sets}
	We may provide the elements of a set:
	\begin{itemize}
	  \item \underline{Intensional definition}: by giving a property they all meet\\(\textit{e.g., even numbers from 1 to 10})
		\item \underline{Extensional definition}: by listing all the elements in the set\\(\textit{e.g.,$\{2,4,6,8,10\}$}). The order in which the different elements are written has no meaning.
	\end{itemize}
\end{block}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Sets}

\begin{ceudef}[Subset and proper subset]
	$B$ is \textbf{subset} of $A$ (denoted $B\subseteq A$ or $A\supseteq B$) if all the elements of $B$ are also elements of $A$. $B$ is a \textbf{proper subset} of $A$ if $B$ is a subset of $A$ and $B$ is different from $A$ ($B\subset A$ or $A\supset B$).
\end{ceudef}

\begin{block}{Properties}
	\begin{itemize}
		\item $A$ is an improper subset of $A$.
		\item $\emptyset$ is a proper subset of $A$.
	\end{itemize}
\end{block}

\begin{ceudef}[Power set (Partes de un conjunto)] 
	The set of all subsets of a set $A$ is called the \textbf{power set} of $A$.
\end{ceudef}

\begin{exampleblock}{Example}
	Let $A=\{1,2,3\}$ the power set of $A$ is
	\begin{center}
		$P(A)=\left\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\right\}$
	\end{center}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Sets}

\begin{ceudef}[Cartesian product]
	The cartesian product of the sets $A$ and $B$ is the set of all ordered pairs in which the first element comes from $A$ and the second element comes from $B$.
	\begin{center}
		$A\times B=\{(a,b)|a\in A, b\in B\}$
	\end{center}
	Note that because of the ordered nature of the pair $A\times B \neq B \times A$.
\end{ceudef}

\begin{exampleblock}{Example}
	Let $A=\{1,2,3\}$ and $B=\{4,5\}$. 
	\begin{center}
		$A\times B=\left\{(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)\right\}$
	\end{center}
\end{exampleblock}

\begin{ceudef}[Cardinality]
	The cardinality of a set is the number of elements it has.
\end{ceudef}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Sets}
\begin{ceudef}[Disjoint sets]
	Two sets are disjoint if they do not have any element in common.
\end{ceudef}

\begin{exampleblock}{Some useful sets}
	\begin{itemize}
		\item Integer numbers: $\mathbb{Z}=\{...,-2,-1,0,1,2,...\}$, $|\mathbb{Z}|=\aleph_0$
		\item Natural numbers, positive integers: $\mathbb{N}=\mathbb{Z}^+=\{1,2,3,...\}$, $|\mathbb{N}|=\aleph_0$
		\item Negative integers: $\mathbb{Z}^-=\{...,-3,-2,-1\}$, $|\mathbb{Z}^-|=\aleph_0$
		\item Non-null integers: $\mathbb{Z}^*=\mathbb{Z}-\{0\}=\{...,-2,-1,1,2,...\}$, $|\mathbb{Z}^*|=\aleph_0$
		\item Rational numbers: $\mathbb{Q}$, $|\mathbb{Q}|=\aleph_0$
		\item Real numbers: $\mathbb{R}$, $|\mathbb{R}|=\aleph_1$
		\item Interval: $[0,1]$, $|[0,1]|=\aleph_1$
		\item Complex numbers: $\mathbb{C}=\{a+bi | a,b\in \mathbb{R}\}$, $|\mathbb{C}|=\aleph_1$
	\end{itemize}
\end{exampleblock}

\end{frame}

% ==============================================
\subsection{Relations and functions} 
\Outline

\begin{frame}\frametitle{Relations}

\begin{ceudef}[Relation]
	A \textbf{relation} $a R b$ is a subset of the cartesian product $A\times B$.
\end{ceudef}

\begin{exampleblock}{Example}
	\begin{center}
		\includegraphics[height=4cm]{figRelation2.jpg}
	\end{center}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Functions}

\begin{ceudef}[Function]
	A \textbf{function} $f:X\rightarrow Y$ is a relation between $X$ and $Y$ in which each $x\in X$ appears at most in one of the pairs $(x,y)$. We may write
	\begin{center}
	  $(x,y)\in f$ or $f(x)=y$
	\end{center}
	The \textbf{domain} of $f$ is $X$, the \textbf{codomain} of $f$ is $Y$. The \textbf{support} of $f$ is the set of all those values in $X$ for which there exists a pair $(x,y)$. The \textbf{range} of $f$ are all values in $Y$ for which there exists at least one pair $(x,y)$.
\end{ceudef}

\begin{exampleblock}{Example}
	\begin{center}
		\begin{tabular}{c}
			$\begin{array}{rcl}f:\mathbb{R}&\rightarrow&\mathbb{R}\\ f(x)&=&x^3\end{array}$\\
			$(2,8)\in f \Leftrightarrow f(2)=8$\\
			\hline
			$\begin{array}{rcl}+:\mathbb{R}\times\mathbb{R}&\rightarrow&\mathbb{R}\end{array}$\\
			$((2,3),5)\in + \Leftrightarrow +((2,3))=5 \Leftrightarrow 2+3=5$\\
		\end{tabular}
	\end{center}
\end{exampleblock}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Classification of functions}
	\begin{ceudef}
		Functions can be classified as \textbf{surjective, injective or bijective}:
		\begin{description}
			\item[\textbf{Surjective}:] A function is surjective if every point of the codomain has \textbf{at least one} point of the domain that maps onto it. They are also called \textbf{onto} functions.
			\item[\textbf{Injective}:] A function is injective if every point of the codomain has \textbf{at most one} point in the domain that maps onto it. They are also called \textbf{one-to-one} functions.
			\item[\textbf{Bijective}:] A function is bijective if it is injective and surjective. 
		\end{description}
		\begin{center}
			\includegraphics[scale=0.35]{figClassification.jpg}
		\end{center}
		
	\end{ceudef}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Inverse function}
\begin{ceudef}[Inverse function]
	Consider an injective function $f:X\rightarrow Y$. $f^{-1}:Y\rightarrow X$ is the \textbf{inverse} of $f$ iff
	\begin{center}
		$(x,y)\in f \Rightarrow (y,x)\in f^{-1}$
	\end{center}
\end{ceudef}
\begin{exampleblock}{Example}
	\begin{itemize}
		\item $f(x)=x+3 \Rightarrow f^{-1}(y)=y-3$
		\item $f(x)=x^3 \Rightarrow f^{-1}(y)=y^{\frac{1}{3}}$
		\item $f(x)=x^2$ is not invertible because it is not injective ($f(-2)=f(2)=4$)
	\end{itemize}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Inverse function}
\begin{ceuthm}
	\begin{itemize}
		\item If $f$ is invertible, its inverse is unique.
		\item If $f$ is bijective, so is $f^{-1}$.
		\item $X$ and $Y$ have the same cardinality if there exists a bijective function between the two.
	\end{itemize}
\end{ceuthm}
\begin{exampleblock}{Example}
  Consider the following function $f: \mathbb{Z} \rightarrow \mathbb{N}$
	\begin{center}
		$\begin{array}{rrrrrrrr}
		   0 & -1 & 1 & -2 & 2 & -3 & 3 & ... \\
		   0 &  1 & 2 &  3 & 4 &  5 & 6 & ... \\
		\end{array}$\\
		$f=\left\{(0,0), (-1,1), (1,2), (-2,3), (2,4), (-3,5), (3,6), ...  \right\}$
	\end{center}
	$f$ is bijective. Consequently, $\mathbb{Z}$ has the same cardinality as $\mathbb{N}$.
\end{exampleblock}

\end{frame}

% ==============================================
\subsection{Partitions and equivalence relationships} 
\Outline

\begin{frame}\frametitle{Partition}
\begin{ceudef}[Partition]
	A partition of a set $S$ is a collection of non-empty subsets such that each element of $S$ belongs to one and only one subset (cell) of the partition. We denote as $\bar{x}$ the 
	subset that contains the element $x$. All cells in a partition are disjoint to any other cell.
\end{ceudef}
\begin{exampleblock}{Examples}
	\begin{itemize}
		\item We may partition the set of natural numbers into the subset of even numbers ($\{2,4,6,...\}$) and the subset of odd numbers ($\{1,3,5,...\}$).
		\item We may partition the set of integer numbers into the subset of all multiples of 3 ($\{...,-6,-3,0,3,6,...\}$), the subset of all numbers whose remainder after dividing by 3 is 1 ($\{...,-5,-2,1,4,7,...\}$), and the subset of all numbers whose remainder after dividing by 3 is 2 ($\{...,-4,-1,2,5,8,...\}$).
	\end{itemize}
\end{exampleblock}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Equivalence relation}
\begin{ceudef}[Equivalence relation]
	$R$ is an \textbf{equivalence relation} in $S$ if it verifies:
	\begin{enumerate}
		\item R is \textbf{reflexive}: $x R x$
		\item R is \textbf{symmetric}: $x R y \Rightarrow y R x$
		\item R is \textbf{transitive}: $x R y, y R z \Rightarrow x R z$
	\end{enumerate}
\end{ceudef}

\begin{exampleblock}{Examples}
	\begin{enumerate}
		\item $=$ is an equivalence relation.
		\item Congruence modulo n is an equivalence relation (two numbers are related if they have the same remainder after dividing by $n$)\\
		      Example: 1 and 4 have remainder 1 after dividing by 3. We write\\
					\begin{center}
						$1 \equiv 4 (mod 3)$
					\end{center}
		\item $\forall n,m\in \mathbb{Z}\quad n R m \Leftrightarrow nm\geq 0$ is not an equivalence relationship because it is not transitive (e.g., $-3 R 0$, $0 R 5$ but $-3 \cancel{R} 5$).
	\end{enumerate}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Partition and equivalence relation}
\begin{ceuthm}
	Let $S$ be a non-empty set, and $R$ an equivalence relation defined on $S$. Then $R$ partitions $S$ with the cells
	\begin{center}
		$\bar{a}=\{x \in S| x R a\}$
	\end{center}
	Additionally, we may define another equivalence relation $\sim$
	\begin{center}
		$a \sim b \Leftrightarrow \bar{a}=\bar{b}$
	\end{center}
\end{ceuthm}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Partition and equivalence relation}

\begin{exampleblock}{Example}
	Congruence modulo 3 is an equivalence relation in $\mathbb{Z}$ (two numbers are related if they have the same remainder after dividing by 3)\\
		\begin{center}
			$\bar{0}=\{...,-6,-3,0,3,6,...\}$\\
			$\bar{1}=\{...,-5,-2,1,4,7,...\}$\\
			$\bar{2}=\{...,-4,-1,2,5,8,...\}$\\
		\end{center}
	Additionally
		\begin{center}
			$...=\bar{0}=\bar{3}=\bar{6}=... \Rightarrow 0 \sim 3 \sim 6 \sim ...$\\
			$...=\bar{1}=\bar{4}=\bar{7}=... \Rightarrow 1 \sim 4 \sim 7 \sim ...$\\
			$...=\bar{2}=\bar{5}=\bar{8}=... \Rightarrow 2 \sim 5 \sim 8 \sim ...$\\
		\end{center}
	and
		\begin{center}
			$\mathbb{Z}=\bar{0} \cup \bar{1} \cup \bar{2}$\\
		\end{center}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Partition and equivalence relation}

\begin{exampleblock}{Example}
  Consider the cartesian product $\mathbb{Z}\times (\mathbb{Z}-\{0\})$. Let $(m_1,n_1)$ and $(m_2,n_2)$ be two ordered sets of this cartesian product. Consider now the equivalence
	relation
	\begin{center}
	 $(m_1,n_1)\sim(m_2,n_2) \Leftrightarrow m_1n_2-m_2n_1=0$
	\end{center}
	The set of rational numbers is formally defined $\mathbb{Q}$ as the set of equivalence classes of $\mathbb{Z}\times (\mathbb{Z}-\{0\})$ under the relation $\sim$.
\end{exampleblock}

\end{frame}

% ==============================================
\subsection{Binary operations} 
\Outline

\begin{frame}\frametitle{Binary operations}
\begin{block}{Introduction}
	\textbf{What is addition?}\\
	\begin{columns}
		\begin{column}{9cm}
			Let us assume that we arrive to a classroom in Mars, and that martians are learning to add. The teacher says
			\begin{center}
				Gloop, poyt
			\end{center}
			and the students reply:
			\begin{center}
				Bimt.
			\end{center}
			Then, the teacher says:
			\begin{center}
				Ompt, gaft
			\end{center}
			and the students reply:
			\begin{center}
				Poyt.
			\end{center}
		\end{column}
		\begin{column}{2cm}
			\includegraphics[width=2cm]{figMartian.png}
		\end{column}
	\end{columns}
	We don't know what they do but it seems that when the teacher gives two elements, students respond with another element.
\end{block}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Binary operations}
\begin{block}{Introduction (continued)}
	\textbf{What is addition?}\\
			This is what we do when we say ``three plus four'', ``seven''. And we may not use any two elements (``three plus apples'' is not defined). We can 
			only use elements on a given set. This is what we formally call a binary operation.
\end{block}

\begin{ceudef}[Binary operation]
	A binary operation on a set $S$ is a function:
	\begin{center}
		$\begin{array}{rcl}
					*:S\times S&\rightarrow&S\\
					*(a,b)&=&a*b\\
				\end{array}$
	\end{center}
\end{ceudef}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Binary operations}
\begin{exampleblock}{Examples}
  The following binary operations are all different:
	\begin{center}
		$\begin{array}{l}
		   +: \mathbb{R}\times\mathbb{R} \rightarrow \mathbb{R} \\
		   +: \mathbb{Z}\times\mathbb{Z} \rightarrow \mathbb{Z} \\
		   +: \mathcal{M}_{m\times n}(\mathbb{R})\times\mathcal{M}_{m\times n}(\mathbb{R}) \rightarrow \mathcal{M}_{m\times n}(\mathbb{R}) \\
			\end{array}$
	\end{center}
	The following is not a binary operation because it is not well defined
	\begin{center}
		$+: \mathcal{M}(\mathbb{R})\times\mathcal{M}(\mathbb{R}) \rightarrow \mathcal{M}(\mathbb{R})$\\
	\end{center}
	we don't know how to add a $2\times 2$ matrix with a $3\times 3$ one.
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Closed set}
\begin{ceudef}
  Let $S$ be a set and $H$ a subset of $S$. $H$ is said to be \textbf{closed with respect to the operation} $*$ defined in $S$ iff
	\begin{center}
		$\forall a,b\in H \quad a*b\in H$
	\end{center}
	Then we may define the binary operation in $H$:
	\begin{center}
		$\begin{array}{rcl}
					*:H\times H&\rightarrow&H\\
					*(a,b)&=&a*b\\
				\end{array}$
	\end{center}
	which is called the \textbf{binary operation induced} in $H$.
\end{ceudef}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Closed set}
\begin{exampleblock}{Example}
  Let $S=\mathbb{Z}$ and $H=\{n^2|n\in\mathbb{Z}^+\}=\{1,4,9,16,25,36,...\}$. $H$ is not closed with respect to addition. For example:
	\begin{center}
		$\begin{array}{c}1\in H \\ 4\in H\end{array}$
		but
		$1+4 \notin H$
	\end{center}
\end{exampleblock}

\begin{exampleblock}{Example}
  Let $S=\mathbb{Z}$ and $H=\{n^2|n\in\mathbb{Z}^+\}=\{1,4,9,16,25,36,...\}$. $H$ is closed with respect to multiplication. For example:
	\begin{center}
		$\begin{array}{c}n^2\in H \\ m^2\in H\end{array}$
		and
		$n^2\cdot m^2 = (nm)^2 \in H$
	\end{center}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Closed set}
\begin{exampleblock}{Example}
  Let $S$ be the set of \textbf{real-valued functions with a single real argument} $S=\{\mathbb{R}\rightarrow \mathbb{R}\}$. Let us define the \textbf{addition} of functions as
	\begin{center}
		$\begin{array}{rcl}
					+:(\mathbb{R}\rightarrow \mathbb{R})\times(\mathbb{R}\rightarrow \mathbb{R})&\rightarrow&\mathbb{R}\rightarrow \mathbb{R}\\
					(f+g)(x)&=&f(x)+g(x)\\
				\end{array}$
	\end{center}
	Similarly for the \textbf{multiplication} and \textbf{subtraction} of functions. Let us define the \textbf{composition} of functions as 
	\begin{center}
		$\begin{array}{rcl}
					\circ:(\mathbb{R}\rightarrow \mathbb{R})\times(\mathbb{R}\rightarrow \mathbb{R})&\rightarrow&\mathbb{R}\rightarrow \mathbb{R}\\
					(f\circ g)(x)&=&f(g(x))\\
				\end{array}$
	\end{center}
	$S$ is closed with respect to addition, subtraction, multiplication and composition.
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Definition of a binary operation}
\begin{exampleblock}{Example}
  To define a binary operation either we give the full table (\textbf{intensional definition}) as in
	\begin{center}
		$\begin{array}{c|ccc}
		   a*b & b=0 & b=1 & b=2 \\
			 \hline
			 a=0 & 0 & 1 & 2 \\
			 a=1 & 1 & 2 & 0 \\
			 a=2 & 2 & 0 & 1 
		\end{array}$ or
		$\begin{array}{c|ccc}
		   a\triangle b & b=0 & b=1 & b=2 \\
			 \hline
			 a=0 & 1 & 2 & 0 \\
			 a=1 & 1 & 1 & 2 \\
			 a=2 & 0 & 0 & 2 
		\end{array}$
	\end{center}
	or we give a rule to compute it (\textbf{extensional definition}) as in
	\begin{center}
		$a*b=(a+b)\; \mathrm{mod}\; 3$
	\end{center}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Properties of a binary operation}
\begin{ceudef}[Commutativity]
	A binary operation is \textbf{commutative} iff
	\begin{center}
		$a*b=b*a$
	\end{center}
\end{ceudef}

\begin{exampleblock}{Example}
	$*$ is commutative because its definition table is symmetric with respect to the main diagonal, but $\triangle$ is not commutative.
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Properties of a binary operation}
\begin{ceudef}[Associativity]
	A binary operation is \textbf{associative} iff
	\begin{center}
		$(a*b)*c=a*(b*c)$
	\end{center}
\end{ceudef}

\begin{exampleblock}{Example}
	$\triangle$ is not associative because
	\begin{center}
		$(0\triangle 0)\triangle 0=1 \triangle 0 = 1$\\
		$0\triangle (0\triangle 0)=0 \triangle 1 = 2$\\
	\end{center}
	But $*$ is associative
	\begin{center}
		$(0*0)*0=0*0=0$\\
		$0*(0*0)=0*0=0$\\
	\end{center}
	We would have to test all possible triples, but after a a little bit of work we could show that $*$ is associative.
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Properties of a binary operation}
\begin{exampleblock}{Example}
	Function composition is associative although not commutative.\\
	\underline{\textit{Proof}}\\
	Function composition is not commutative
	\begin{center}
		$(f\circ g)(x)=f(g(x))\neq g(f(x))=(g\circ f)(x)$
	\end{center}
	Function composition is associative
	\begin{center}
		$((f\circ g)\circ h)(x)=(f\circ g)(h(x))=f(g(h(x)))=f((g\circ h)(x))=(f\circ(g\circ h))(x)$
	\end{center}
	
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Properties of a binary operation}
\begin{exampleblock}{Example}
	A function may not be well defined. For instance, 
	\begin{center}
		$\begin{array}{rcl}
					/:\mathbb{Q}\times\mathbb{Q}&\rightarrow&\mathbb{Q}\\
					a/b&=&\frac{a}{b}\\
				\end{array}$
	\end{center}
	is not well defined for $b=0\in \mathbb{Q}$
\end{exampleblock}

\begin{exampleblock}{Example}
	A function may not be closed in $S$. For instance,
	\begin{center}
		$\begin{array}{rcl}
					/:\mathbb{Z}\times\mathbb{Z}&\rightarrow&\mathbb{Z}\\
					a/b&=&\frac{a}{b}\\
				\end{array}$
	\end{center}
	is not closed because $a=1\in \mathbb{Z}, b=3\in\mathbb{Z}$ but $\frac{1}{3}\notin\mathbb{Z}$.
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Properties of a binary operation}
\begin{ceudef}[Existence of a neutral element]
	A binary operation has a \textbf{neutral element}, $e$, iff
	\begin{center}
		$\forall a\in S \quad a*e=e*a=a$
	\end{center}
\end{ceudef}

\begin{exampleblock}{Example}
	0 is the neutral element of addition in $\mathbb{R}$ because
	\begin{center}
		$\forall r \in \mathbb{R} \quad r+0=0+r=r$
	\end{center}
	1 is the neutral element of multiplication in $\mathbb{R}$ because
	\begin{center}
		$\forall r \in \mathbb{R} \quad r\cdot 1=1 \cdot r=r$
	\end{center}
	Addition in $\mathbb{N}$ has no neutral element since $0\notin \mathbb{N}$.
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Properties of a binary operation}
\begin{ceudef}[Existence of an inverse element]
	A binary operation has an \textbf{inverse element} iff
	\begin{center}
		$\forall a\in S \quad \exists b\in S | a*b=b*a=e$
	\end{center}
	being $e$ the neutral element of $*$.
\end{ceudef}

\begin{exampleblock}{Example}
	The inverse element of 2 with respect to addition in $\mathbb{R}$ is -2 because
	\begin{center}
		$2 + (-2) = (-2) + 2 = 0$
	\end{center}
	The inverse element of 2 with respect to multiplication in $\mathbb{R}$ is $\frac{1}{2}$ because
	\begin{center}
		$2 \cdot \frac{1}{2} = \frac{1}{2} \cdot 2 = 1$
	\end{center}
	Multiplication in $\mathbb{N}$ has no inverse element since $\forall n \in \mathbb{N} \quad \frac{1}{n}\notin \mathbb{N}$.
\end{exampleblock}

\end{frame}

% ==============================================
\subsection{Groups and subgroups} 
\Outline

\begin{frame}\frametitle{Groups and subgroups}
\begin{block}{Introduction}
	Groups and subgroups are algebraic structures. They are the ones that allow solving equations like
	\begin{center}
		$x+x=a \Rightarrow x=\frac{a}{2}$
	\end{center}
	and that the equation
	\begin{center}
		$x\cdot x=a$
	\end{center}
	does not have a solution in $\mathbb{R}$ if $a<0$. 
	
	We'll see that defining a group
	amounts to define the elements belonging to the group as well as the operations that can be used with them.
\end{block}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Groups}
\begin{ceudef}[Group]
	Given a set $S$ and a binary operation $*$ defined on $S$, the pair $(S,*)$ is a \textbf{group} if $G$ is closed under $*$ and
	\begin{description}
		\item[G1.] $*$ is associative in $S$
		\item[G2.] $*$ has a neutral element in $S$
		\item[G3.] $*$ has an inverse element in $S$
	\end{description}
\end{ceudef}

\begin{ceudef}[Abelian group]
	$(S,*)$ is an \textbf{abelian group} if $(S,*)$ is a group and $*$ is commutative.
\end{ceudef}

\begin{ceudef}[Subgroup]
	Let $(S,*)$ be a group. Let $H$ be a subset of $S$, $H\subseteq S$, and $*_H$ be the $*$ induced operation in $H$. The pair $(H,*_H)$ is a subgroup
	of $(S,*)$ if it verifies the conditions to be a group.
\end{ceudef}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Groups}
\begin{exampleblock}{Example}
	Consider $S=\{z\in\mathbb{C}|z=e^{i\varphi}\quad \forall \varphi\in\mathbb{R}\}$. $(U,\cdot)$ is a group.
	\begin{center}
		\includegraphics[scale=0.3]{figUnitCircle.png}
	\end{center}
	\underline{\textit{Proof}}\\
	\begin{description}
		\item[G1.] $\cdot$ is associative in $S$\\
			\begin{center}
				$z_1(z_2z_3)=e^{i\varphi_1}(e^{i\varphi_2}e^{i\varphi_3})=e^{i\varphi_1}(e^{i(\varphi_2+\varphi_3)})=e^{i(\varphi_1+\varphi_2+\varphi_3)}$\\
				$(z_1z_2)z_3=(e^{i\varphi_1}e^{i\varphi_2})e^{i\varphi_3}=(e^{i\varphi_1+\varphi_2})e^{i\varphi_3}=e^{i(\varphi_1+\varphi_2+\varphi_3)}$
			\end{center}
	\end{description}
	
\end{exampleblock}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Groups}
\begin{exampleblock}{Example (continued)}
	\underline{\textit{Proof}}\\
	\begin{description}
		\item[G2.] $\cdot$ has a neutral element in $S$\\
		  $1=e^{i0} \in S$
			\begin{center}
				$z\cdot 1=e^{i\varphi}e^{i0}=e^{i(\varphi+0)}=e^{i\varphi}=z$\\
				$1\cdot z=e^{i0}e^{i\varphi}=e^{i(0+\varphi)}=e^{i\varphi}=z$\\
			\end{center}
		\item[G3.] $\cdot$ has an inverse element in $S$\\
		  For each $z=e^{i\varphi}$, its inverse element with respect to $\cdot$ is $z^{-1}=e^{-i\varphi}$
			\begin{center}
				$zz^{-1}=e^{i\varphi}e^{-i\varphi}=e^{i(\varphi-\varphi)}=e^{i0}=1$\\
				$z^{-1}z=e^{-i\varphi}e^{i\varphi}=e^{i(-\varphi+\varphi)}=e^{i0}=1$\\
			\end{center}
	\end{description}
	
\end{exampleblock}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Groups}
\begin{exampleblock}{Example}
	\begin{itemize}
		\item $(\mathbb{N},+)$ is not a group because it has no neutral element.
		\item $(\mathbb{N}\cup\{0\},+)$ is not a group because it has no inverse element.
		\item $(\mathbb{Z},+)$, $(\mathbb{Q},+)$, $(\mathbb{R},+)$, $(\mathbb{C},+)$ and $(\mathbb{R}^n,+)$ are abelian groups.
		\item $(\mathcal{M}_{m\times n},+)$ is an abelian group.
		\item $(\mathbb{R},\cdot)$ is not a group because $0$ has no inverse.
		\item $(\mathcal{M}_{n\times n}(\mathbb{R})),\cdot)$ is not a group because $\begin{pmatrix} 0 & 0 & ... & 0 \\ 0 & 0 & ... & 0 \\ ... & ... & ... & ... \\ 0 & 0 & ... & 0 \end{pmatrix}$
		      has no inverse.
		\item Let $S\in\mathcal{M}_{n\times n}(\mathbb{R})$ be the set of invertible matrices of size $n\times n$. $(S,\cdot)$ is a group (although not abelian).
		      It is called the General Linear Group of degree $n$ ($GL(n,\mathbb{R})$).
	\end{itemize}
	
\end{exampleblock}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Groups}
\begin{exampleblock}{Example}
	The existence of groups is what allows us to solve equations. For instance, consider the equation
	\begin{center}
		$5+x=2$
	\end{center}
	and its solution in the group $(\mathbb{Z},+)$
	\begin{center}
		$\begin{array}{rcll}
		  5+x&=&2& \text{[Addition of the inverse of 5 with respect to + in both sides]} \\
		  -5+(5+x)&=&-5+2& \text{[Addition is associative ]} \\
		  (-5+5)+x&=&-3& \text{[Definition of inverse]} \\
		  0+x&=&-3& \text{[Definition of neutral element]} \\
		  x&=&-3& \\
		 \end{array}$
	\end{center}
\end{exampleblock}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Groups}
\begin{exampleblock}{Example}
	Consider the equation
	\begin{center}
		$2x=3$
	\end{center}
	and its solution in the group $(\mathbb{Q},\cdot)$
	\begin{center}
		$\begin{array}{rcll}
		  2x&=&3& \text{[Multiplication by the inverse of 2 in both sides]} \\
		  \frac{1}{2}(2x)&=&\frac{1}{2}3& \text{[Multiplication is associative ]} \\
		  (\frac{1}{2}2)x&=&\frac{2}{3}& \text{[Definition of inverse]} \\
		  1x&=&\frac{2}{3}& \text{[Definition of neutral element]} \\
		  x&=&\frac{2}{3}& \\
		 \end{array}$
	\end{center}
\end{exampleblock}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Groups}
\begin{ceuthm}[Cancellation laws]
  Given any group $(S,*)$, $\forall a,b,c \in S$ it is verified
	\begin{itemize}
		\item Left cancellation: $a*b=a*c \Rightarrow b=c$
		\item Right cancellation: $b*a=c*a \Rightarrow b=c$
	\end{itemize}
\end{ceuthm}

\begin{ceuthm}[Existance of a unique solution of linear equations]
  Given any group $(S,*)$, $\forall a,b \in S$ the linear equations
	\begin{center}
		$a*x=b$ and $y*a=b$
	\end{center}
	always have a unique solution in $S$.
\end{ceuthm}

\begin{ceuthm}[Properties of the inverse]
  Given any group $(S,*)$, $\forall a \in S$ its inverse is unique and $\forall a,b\in S$
	\begin{center}
		$(a*b)^{-1}=(b^{-1})*(a^{-1})$
	\end{center}
\end{ceuthm}

\end{frame}

% ==============================================
\subsection{Homomorphisms and isomorphisms} 
\Outline

\begin{frame}\frametitle{Homomorphisms}
\begin{exampleblock}{Example}
	Consider the sets $S=\{a,b,c\}$ and $S'=\{A,B,C\}$ with the operations $*:S\times S\rightarrow S$ and $*':S'\times S'\rightarrow S'$
	\begin{center}
		$\begin{array}{c|ccc}
		   x*y & y=a & y=b & y=c \\
			 \hline
			 x=a & a & b & c \\
			 x=b & b & c & a \\
			 x=c & c & a & b 
		\end{array}$ and
		$\begin{array}{c|ccc}
		   x*'y & y=A & y=B & y=C \\
			 \hline
			 x=A & A & B & C \\
			 x=B & B & C & A \\
			 x=C & C & A & B 
		\end{array}$
	\end{center}
	We may construct a function that ``translates'' elements in $S$ into elements in $S'$ with the ``same properties''.
	\begin{center}
		$\begin{array}{rcl}
					\phi:S&\rightarrow&S'\\
					\phi(a)&=&A\\
					\phi(b)&=&B\\
					\phi(c)&=&C\\
				\end{array}$
	\end{center}
	We note that
	\begin{center}
		$b*c=a \Rightarrow \phi(b)*'\phi(c)=\phi(a) \Rightarrow B*'C=A$
	\end{center}
	
\end{exampleblock}
\end{frame}

% ==============================================
\begin{frame}\frametitle{Homomorphisms}
\begin{ceudef}[Group homomorphism]
	Given two groups $(S,*)$ and $(S',*')$, the function $\phi:S\rightarrow S'$ is a \textbf{group homomorphism} iff $\forall a,b\in S$
	\begin{center}
		$\phi(a*b)=\phi(a)*'\phi(b)$
	\end{center}
\end{ceudef}

\begin{ceudef}[Group isomorphism]
	Given two groups $(S,*)$ and $(S',*')$, the function $\phi:S\rightarrow S'$ is a group isomorphism iff it is a group homomorphism and it is bijective.
\end{ceudef}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Homomorphisms}
\begin{exampleblock}{Example}
	Consider the two groups $(\mathbb{R}^n,+)$ and $(\mathbb{R}^m,+)$ and a matrix $A\in\mathcal{M}_{m\times n}(\mathbb{R})$. The application
	\begin{center}
		$\begin{array}{rcl}
					\phi:\mathbb{R}^n&\rightarrow&\mathbb{R}^m\\
					\phi(\mathbf{x})&=&A\mathbf{x}\\
				\end{array}$
	\end{center}
	is a group homomorphism because
	\begin{center}
		$\phi(\mathbf{u}+\mathbf{v})=A(\mathbf{u}+\mathbf{v})=A\mathbf{u}+A\mathbf{v}=\phi(\mathbf{u})+\phi(\mathbf{v})$
	\end{center}
\end{exampleblock}
\begin{exampleblock}{Example}
	Consider the two groups $(GL(n,\mathbb{R}),\cdot)$ and $(\mathbb{R},\cdot)$. The application
	\begin{center}
		$\begin{array}{rcl}
					\phi:GL(n,\mathbb{R})&\rightarrow&\mathbb{R}\\
					\phi(A)&=&\det\{A\}\\
				\end{array}$
	\end{center}
	is a group homomorphism because
	\begin{center}
		$\phi(AB)=\det\{AB\}=\det\{A\}\det\{B\}=\phi(A)\cdot\phi(B)$
	\end{center}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Homomorphisms}
\begin{ceuthm}
	Let $\phi:S\rightarrow S'$ be a group homomogrphism between two groups. Then,
	\begin{itemize}
		\item $\phi(e)=e'$
		\item $\phi(a^{-1})=(\phi(a))^{-1}$
	\end{itemize}
\end{ceuthm}
\begin{ceudef}[Kernel of a group homomorphism]
	Let $\phi:S\rightarrow S'$ be a group homomogrphism between two groups. Then, the kernel of $\phi$ is the set
	\begin{center}
		$\mathrm{Ker}\{\phi\}=\{x\in S| \phi(x)=e'\}$
	\end{center}
\end{ceudef}
\begin{exampleblock}{Example}
	Let $\phi(\mathbf{x})=A\mathbf{x}$. Then,
	\begin{center}
		$\mathrm{Ker}\{\phi\}=\{x\in \mathbb{R}^n| A\mathbf{x}=\mathbf{0}\}=\mathrm{Nul}\{A\}$
	\end{center}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Isomorphisms}

\begin{ceuthm}[Isomorphisms and cardinality]
	If two groups $(S,*)$ and $(S',*')$ are isomorph (i.e., there exists an isomorphism between the two groups), then $S$ and $S'$ have the same cardinality.
	\begin{center}
		\includegraphics[height=3cm]{figIsomorphism.jpg}
	\end{center}
\end{ceuthm}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Isomorphisms}

\begin{exampleblock}{Example}
	\begin{itemize}
		\item $\mathbb{Q}$ and $\mathbb{R}$ cannot be isomorph because the cardinality of $\mathbb{Q}$ is $\aleph_0$ and the cardinality of $\mathbb{R}$ is $\aleph_1$.
		\item There are as many natural numbers as natural even numbers. In other words, the cardinality of $\mathbb{N}$ and $2\mathbb{N}$ are the same. The reason is that
		      the function $\phi(n)=2n$ is an isomorphism between $\mathbb{N}$ and $2\mathbb{N}$.
	\end{itemize}
\end{exampleblock}

\begin{exampleblock}{Example}
	Consider the set $\mathbb{R}_c=[0,c)\in \mathbb{R}$ and the operation $x +_c y = (x+y)\;\mathrm{mod}\; c$. The pair $(\mathbb{R}_c,+_c)$ is a group. Consider now 
	the two particular cases $(\mathbb{R}_{2\pi},+_{2\pi})$ and $(\mathbb{R}_1,+_1)$ and the mapping
	\begin{center}
		$\begin{array}{rcl}
					\phi:\mathbb{R}_{2\pi}&\rightarrow&\mathbb{R}_1\\
					\phi(x)&=&\frac{x}{2\pi}\\
				\end{array}$
	\end{center}
	$\phi$ is an isomorphism between  $(\mathbb{R}_{2\pi},+_{2\pi})$ and $(\mathbb{R}_1,+_1)$. In fact, all $(\mathbb{R}_c,+_c)$ groups are isomorph to any other $(\mathbb{R}_{c'},+_{c'})$ group.
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Isomorphisms}

Cardinality is a \textit{group property}. The nice things about isomorphisms is that they preserve group properties.

\begin{ceuthm}
	If two groups $(S,*)$ and $(S',*')$ are isomorph, then
	\begin{itemize}
		\item If $*$ is commutative, so is $*'$.
		\item If there is an order relation in $S$, it can be ``translated'' into an order relation in $S'$.
		\item If $\forall s\in S$ there exists a solution in $S$ of the equation $x*x=s$, then $\forall s'\in S'$ there exists a solution in $S'$ of the equation $x'*'x'=s'$.
		\item If $\forall a,b\in S$ there exists a solution in $S$ of the equation $a*x=b$, then $\forall a',b'\in S'$ there exists a solution in $S'$ of the equation $a'*'x'=b'$.
		\item The kernel of any isomorphism $\phi$ between $(S,*)$ and $(S',*')$ is $\mathrm{Ker}\{\phi\}=\{e\}$ being $e$ the neutral element of $*$ in $S$.
	\end{itemize}
\end{ceuthm}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Isomorphisms}
\begin{exampleblock}{Example}
	$(\mathbb(Z),+)$ is not isomorph to $(\mathbb(Q),+)$ because the equation
	\begin{center}
	   $x+x=s$
	\end{center}
	has a solution in $\mathbb{Q}$ for any $s\in\mathbb{Q}$ (that is $x=\frac{s}{2}$), but it does not have a solution in $\mathbb{Z}$ for any $s\in\mathbb{Z}$ (it only has a solution in $\mathbb{Z}$ if $s$ is an even number).
\end{exampleblock}

\begin{exampleblock}{Example}
	$(\mathbb(R),\cdot)$ is not isomorph to $(\mathbb(C),\cdot)$ because the equation
	\begin{center}
	   $x\cdot x=z$
	\end{center}
	has two solution in $\mathbb{C}$ for any $z\in\mathbb{C}$ (if $z=re^{i\theta}$, then $x=\pm re^{i\frac{\theta}{2}}$ are the two solutions) , but it does not have a solution in $\mathbb{R}$ for any $z\in\mathbb{R}$ (it only has a solution in $\mathbb{R}$ if $z$ is a non-negative number).
\end{exampleblock}

\end{frame}

% ==============================================
\subsection{Algebraic structures} 
\Outline

\begin{frame}\frametitle{Algebraic structures}

\begin{block}{Algebraic structures}
	\textbf{Algebraic structures} are tools that help us to define operate on numbers and elements within a set, solve equations, etc.
	\begin{center}
	  \includegraphics[width=11cm]{figAlgebraicStructures.png}
	\end{center}
\end{block}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Algebraic structures}

\begin{ceudef}[Ring]
	The tuple $(S,*,\circ)$ is a \textbf{ring} iff
	\begin{description}
	  \item{R1.} $(S,*)$ is an abelian group.
		\item{R2.} $\circ$ is associative.
		\item{R3.} $\circ$ is distributive with respect to $*$, i.e., $\forall a,b,c \in S$
		   \begin{itemize}
				 \item Left-distributive: $a\circ(b*c)=(a\circ b)*(a\circ c)$
				 \item Right-distributive: $(a*b)\circ c=(a\circ c)*(b\circ c)$
			 \end{itemize}
	\end{description}
\end{ceudef}

\begin{exampleblock}{Example}
	\begin{itemize}
		\item $(\mathbb{Z},+,\cdot)$, $(\mathbb{Q},+,\cdot)$, $(\mathbb{R},+,\cdot)$, $(\mathbb{C},+,\cdot)$ are rings.
		\item $(\mathcal{M}_{m\times n}(\mathbb{R}),+,\cdot)$ is a ring.
		\item $(\mathbb{R}\rightarrow\mathbb{R},+,\cdot)$ is a ring.
	\end{itemize}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Algebraic structures}

\begin{ceuthm}[Properties of rings]
	Let $(S,*,\circ)$ be a ring and let $e$ be the neutral element of $*$ in $S$. For any $a\in S$, let $a'$ be the inverse of $a$ with respect to the operation $*$. Then $\forall a,b\in S$
	\begin{itemize}
	  \item $a\circ e = e\circ a= e$.
	  \item $a\circ b'=a'\circ b=(a\circ b)'$
		\item $a'\circ b'=a\circ b$
	\end{itemize}
\end{ceuthm}

\begin{exampleblock}{Example}
	Consider the ring $(\mathbb{R},+,\cdot)$. We are used to the properties $\forall a,b\in\mathbb{R}$
	\begin{itemize}
	  \item $a\cdot 0=0\cdot a=0$.
	  \item $a\cdot (-b)=(-a)\cdot b=-(a\cdot b)$
		\item $(-a)\cdot (-b)=a\cdot b$
	\end{itemize}
	But, as stated by the previous theorem, these are properties of all rings.
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Algebraic structures}

\begin{ceudef}[Kinds of rings]
  A ring $(S,*,\circ)$ is
	\begin{itemize}
		\item \textbf{commutative} iff $\circ$ is commutative.
		\item \textbf{unitary} iff $\circ$ has a neutral element (referred as $1$).
		\item \textbf{divisive} if it is unitary and \\
			\begin{center}
				$\forall a \in S-\{e\}\quad \exists ! a^{-1}\in S, | a \circ a^{-1} = a^{-1} \circ a = 1$
			\end{center}
			That is each element has a multiplicative inverse.
	\end{itemize}
\end{ceudef}

\begin{exampleblock}{Example}
	\begin{itemize}
		\item $(\mathbb{P},+,\cdot)$ the set of polynomials with coefficients from a ring is a ring.
	\end{itemize}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Algebraic structures}

\begin{ceudef}[Field (\textit{cuerpo})]
	A divisive, commutative ring is called a \textbf{field}.
\end{ceudef}

\begin{exampleblock}{Example}
	\begin{itemize}
		\item $(\mathbb{Q},+,\cdot)$, $(\mathbb{R},+,\cdot)$, and $(\mathbb{C},+,\cdot)$ are fields.
		\item $(\mathbb{Z},+,\cdot)$ is not a field because multiplication has not an inverse in $\mathbb{Z}$.
	\end{itemize}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Algebraic structures}

\begin{ceudef}[Vector space over a field]
	Consider a field $(\mathbb{K},*,\circ)$. A \textbf{vector space} over this field is a tuple $(V,+,\cdot)$ so that $V$ is a set whose elements are called vectors,
	and $+: V\times V \rightarrow V$ is a binary operation under which $V$ is closed, $\cdot: \mathbb{K} \times V \rightarrow V$ is an operation between scalars
	in the field ($\mathbb{K}$) and vectors in the vector space ($V$) such that $\forall a,b\in \mathbb{K}, \forall \mathbf{u},\mathbf{v}\in V$
	\begin{description}
		\item{V1.} $(V,+)$ is an abelian group.
		\item{V2.} $(a\cdot \mathbf{u}) \in V$
		\item{V3.} $a\cdot (b\cdot \mathbf{u}) = (a\circ b)\cdot \mathbf{u}$
		\item{V4.} $(a*b)\cdot \mathbf{u}= a\cdot \mathbf{u}+b\cdot \mathbf{u}$
		\item{V5.} $a\cdot (\mathbf{u}+\mathbf{v}) = a\cdot \mathbf{u}+a\cdot \mathbf{v}$
		\item{V6.} $1\cdot \mathbf{u} = \mathbf{u}$
	\end{description}
\end{ceudef}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Algebraic structures}

\begin{exampleblock}{Examples}
	\begin{itemize}
		\item $(\mathbb{R}^n,+,\cdot)$ and $(\mathbb{C}^n,+,\cdot)$.
		\item $(\mathcal{M}_{m\times n}(\mathbb{R}),+,\cdot)$: the set of matrices of a given size with coefficients in a field.
		\item $(\mathbb{P},+,\cdot)$: the set of polynomials with coefficients in a field.
		\item $(\{X\rightarrow V\},+,\cdot)$: the set of all functions from an arbitrary set $X$ onto an arbitrary vector space $V$.
		\item The set of all continuous functions is a vector space.
		\item The set of all linear maps between two vector spaces is also a vector space.
		\item The set of all infinite sequences of values from a field is also a vector space.
	\end{itemize}
\end{exampleblock}

\end{frame}

% ==============================================
\begin{frame}\frametitle{Algebraic structures}

\begin{ceudef}[Algebra]
  Consider a vector space $(V,+,\cdot)$ over a field $(\mathbb{K},*,\circ)$ and a binary operation $\bullet: V \times V \rightarrow V$. $(V,+,\cdot,\bullet)$ is an \textbf{algebra} iff
	$\forall a,b\in \mathbb{K}, \forall \mathbf{u},\mathbf{v},\mathbf{w}\in V$
	\begin{description}
		\item{A1.} Left distributivity: $(\mathbf{u}+\mathbf{v})\bullet \mathbf{w}=\mathbf{u}\bullet\mathbf{w}+\mathbf{v}\bullet\mathbf{w}$
		\item{A2.} Right distributivity: $\mathbf{u}\bullet(\mathbf{v}+\mathbf{w})=\mathbf{u}\bullet\mathbf{v}+\mathbf{u}\bullet\mathbf{w}$
		\item{A3.} Compatibility with scalars: $(a\cdot\mathbf{u})\bullet(b\cdot\mathbf{v})=(a\circ b)\cdot(\mathbf{u}\bullet\mathbf{v})$
	\end{description}
\end{ceudef}

\begin{exampleblock}{Examples}
	\begin{itemize}
		\item Real numbers ($\mathbb{R}$) are an algebra (``1D'').
		\item Complex numbers ($\mathbb{C}$) are an algebra (``2D'').
		\item Quaternions are an algebra (``4D'').
	\end{itemize}
\end{exampleblock}

\end{frame}

\OutlineFinal

\end{document}